/**
 * 53. 最大子序和
 */
public class Solution_53 {
    /**
     * 官方题解：动态规划
     * <p>
     * 时间复杂度：O(N)
     * 空间复杂度：O(1)
     */
    public int maxSubArray(int[] nums) {
        int pre = 0, maxAns = nums[0];
        for (int x : nums) {
            pre = Math.max(pre + x, x);
            maxAns = Math.max(maxAns, pre);
        }
        return maxAns;
    }
}
